我們來看到最大公因數(GCD)及最小公倍數(LCM)啦!

最大公因數顧名思義就是兩數或多個數間共同有的因數。

例如，2、4、8，的GCD是2，或6、12，的GCD是6。

學習目標: GCD、LCM的概念及實務

學習難度: ☆☆☆

我們來看它是怎麼被實現出來吧!

Recursion with GCD

#include <iostream>

using namespace std;

int GCD(int num1,int num2)
{
	if(num2==0)
	{
	 return num1;
	} 
	
	return GCD(num2,num1%num2);
}

int main()
{
	cout<<GCD(6,3); //2數最大公因數
    
    cout<<GCD((6,3),3); //3數最大公因數
	
	return 0;
}

最小公倍數是兩個數或多個數最小共同有的倍數。

例如，2、4、8，的LCM是8，或6、12，的LCM是12。

Recursion with LCM

#include <iostream>

using namespace std;

int GCD(int num1,int num2)
{
	if(num2==0)
	{
	 return num1;
	} 
	
	return GCD(num2,num1%num2);
}

int LCM(int num1,int num2) //2數最小公倍數
{
	return((num1*num2)/GCD(num1,num2));
}

int LCM2(int num1,int num2,int num3) //3數最小公倍數
{
	return((num1*num2)/GCD((num1,num2),num3));
}

int main()
{	
	cout<<LCM(6,3);
    
    cout<<LCM2(6,3,3);

	return 0;
}

參考資料:

https://dotblogs.com.tw/peterkyo/2014/05/22/145207